{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Subarray Sums Divisible by K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarraysDivByK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和可被 K 整除的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code>&nbsp;和一个整数 <code>k</code> ，返回其中元素之和可被 <code>k</code>&nbsp;整除的（连续、非空） <strong>子数组</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组的 <strong>连续</strong> 部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [4,5,0,-2,-3,1], k = 5\n",
    "<strong>输出：</strong>7\n",
    "<strong>解释：\n",
    "</strong>有 7 个子数组满足其元素之和可被 k = 5 整除：\n",
    "[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [5], k = 9\n",
    "<strong>输出:</strong> 0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= nums[i] &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>2 &lt;= k &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [subarray-sums-divisible-by-k](https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [subarray-sums-divisible-by-k](https://leetcode.cn/problems/subarray-sums-divisible-by-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,5,0,-2,-3,1]\\n5', '[5]\\n9']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        prefix_sum = 0\n",
    "        count = 0\n",
    "        remainder_count = {0: 1}  # 用于记录余数出现的次数，初始化余数0的次数为1\n",
    "\n",
    "        for num in nums:\n",
    "            prefix_sum = (prefix_sum + num) % k\n",
    "            if prefix_sum in remainder_count:\n",
    "                count += remainder_count[prefix_sum]\n",
    "                remainder_count[prefix_sum] += 1\n",
    "            else:\n",
    "                remainder_count[prefix_sum] = 1\n",
    "\n",
    "        return count\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, A: List[int], K: int) -> int:\n",
    "        A = [x%K for x in A]\n",
    "        D = {0:1}\n",
    "        ret = 0\n",
    "        x = 0\n",
    "        for y in A :\n",
    "            x = (x+y)%K\n",
    "            if D.get(x)!=None :\n",
    "                ret += D[x]\n",
    "                D[x] += 1\n",
    "            else :\n",
    "                D[x] = 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums, k):\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        for i in range(n):\n",
    "            if i>0:\n",
    "                nums[i]+=nums[i-1]\n",
    "            nums[i]%=k\n",
    "        cnt={0:1}\n",
    "        for j in range(0,n):\n",
    "            ncnt=cnt.get(nums[j],0)\n",
    "            cnt[nums[j]]=ncnt+1\n",
    "            ans+=ncnt\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, A: List[int], K: int) -> int:\n",
    "        res = 0\n",
    "        pre_sum = dict([[i, 0] for i in range(K)])\n",
    "        pre_sum[0] += 1\n",
    "        cum = 0\n",
    "        for i in range(len(A)):\n",
    "            cum += A[i]\n",
    "            cum %= K\n",
    "            res += pre_sum[cum]\n",
    "            pre_sum[cum] += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums, k):\n",
    "        diction = {0: [-1]}\n",
    "        pre = 0\n",
    "        ans = 0\n",
    "        for index, num in enumerate(nums):\n",
    "            pre += num\n",
    "            rem = pre % k\n",
    "            if rem in diction.keys():\n",
    "                ans += len(diction[rem])\n",
    "                diction[rem].append(index)\n",
    "            else:\n",
    "                diction[rem] = [index]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums, k):\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        for l in range(n):\n",
    "            if l > 0:\n",
    "                nums[l] += nums[l-1]\n",
    "            nums[l] %= k\n",
    "        cnt = {0 : 1}\n",
    "        for l in range(0, n):\n",
    "            ncnt = cnt.get(nums[l], 0)\n",
    "            cnt[ nums[l] ] = ncnt + 1\n",
    "            ans += ncnt\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        m=len(nums)\n",
    "        pre=[0]*m\n",
    "        pre[0]=nums[0]\n",
    "        for i in range(1,m):\n",
    "            pre[i]=pre[i-1]+nums[i]\n",
    "        for i in range(m):\n",
    "            pre[i]=pre[i]%k\n",
    "        d=defaultdict(list)\n",
    "        for i in range(m):\n",
    "            d[pre[i]].append(i)\n",
    "        ans=len(d[0])\n",
    "        for k in d:\n",
    "            ans+=len(d[k])*(len(d[k])-1)/2\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from itertools import accumulate\n",
    "from typing import List\n",
    "from collections import Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        prefix_sum = list(accumulate(nums))\n",
    "        pre_sum = [i % k for i in prefix_sum]\n",
    "        count = Counter(pre_sum)\n",
    "        if 0 in count:\n",
    "            res += count.get(0)\n",
    "        for k, v in count.items():\n",
    "            if v >= 2:\n",
    "                res += self.com_num(v)\n",
    "        return int(res)\n",
    "\n",
    "    def com_num(self, num):\n",
    "        return num * (num - 1) / 2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total, ans = 0, 0\n",
    "        for elem in nums:\n",
    "            total += elem\n",
    "            modulus = total % k\n",
    "            same = record.get(modulus, 0)\n",
    "            ans += same\n",
    "            record[modulus] = same + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        import itertools\n",
    "        a = list(itertools.accumulate(nums))\n",
    "        a.insert(0,0)\n",
    "        b = []\n",
    "        for i in a:\n",
    "            b.append(i % k)\n",
    "\n",
    "        c = Counter(b)\n",
    "        d = dict.values(c)\n",
    "        res = 0\n",
    "        for i in d:\n",
    "            res += (i * (i - 1)) // 2\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        hashmap = {0:1}\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        for idx,n in enumerate(nums):\n",
    "            pre += n\n",
    "            res += hashmap.get(pre%k,0)\n",
    "            hashmap[pre%k] = hashmap.get(pre%k,0) + 1\n",
    "        \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        out = 0\n",
    "        cur = 0\n",
    "        d = {0:[-1]}\n",
    "        for i in range(len(nums)):\n",
    "            cur += nums[i]\n",
    "            if cur%k not in d:\n",
    "                d[cur%k] = [i]\n",
    "            else:\n",
    "                d[cur%k].append(i)\n",
    "        for x in d:\n",
    "            t = len(d[x])-1\n",
    "            out += t*(t+1)//2\n",
    "        # print(d)\n",
    "        return out\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total, ans = 0, 0\n",
    "        for elem in nums:\n",
    "            total += elem\n",
    "            modulus = total % k\n",
    "            same = record.get(modulus, 0)\n",
    "            ans += same\n",
    "            record[modulus] = same + 1\n",
    "        return ans\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        cnt = Counter()\n",
    "        cnt[0] = 1\n",
    "        s = 0\n",
    "        for x in nums:\n",
    "            s += x\n",
    "            cnt[s % k] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for k, v in cnt.items():\n",
    "            ans += v * (v - 1) // 2\n",
    "        return ans\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0:1}\n",
    "        total, ans = 0,0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "            mod  = total % k \n",
    "            same = record.get(mod, 0)\n",
    "            ans += same\n",
    "            record[mod] = same + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total, ans = 0, 0\n",
    "        for n in nums:\n",
    "            total += n\n",
    "            m = total % k\n",
    "            s = record.get(m, 0)\n",
    "            ans += s\n",
    "            record[m] = s + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        import collections\n",
    "        res, sums = 0, 0\n",
    "        dict = collections.defaultdict(int)\n",
    "        dict[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            sums += nums[i]\n",
    "            if sums % k in dict:\n",
    "                res += dict[sums % k]\n",
    "            dict[sums % k] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, A: List[int], K: int) -> int:\n",
    "        presum = [0] * (len(A)+1)\n",
    "        ans, hashmap = 0, {}\n",
    "        for i in range(len(A)):\n",
    "            presum[i+1] = presum[i] + A[i]\n",
    "        for i in range(len(presum)):\n",
    "            num = presum[i] % K\n",
    "            if num not in hashmap:\n",
    "                hashmap[num] = [i]\n",
    "            else:\n",
    "                ans += len(hashmap[num])\n",
    "                hashmap[num].append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        f = defaultdict(int)\n",
    "        f[0] = 1\n",
    "\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        for i in range(len(nums)):\n",
    "            presum += nums[i]\n",
    "            ans += f[presum%k]\n",
    "\n",
    "            f[presum%k] += 1\n",
    "\n",
    "        return ans   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, A: List[int], K: int) -> int:\n",
    "        pre_sum, result = 0, 0\n",
    "        dic = {0: 1}  # initial\n",
    "\n",
    "        for val in A:\n",
    "            pre_sum = (pre_sum + val) % K  # 累加並對 K取餘\n",
    "            if pre_sum in dic:  # 判斷是否在字典內，即有(同餘的值)\n",
    "                result += dic[pre_sum]  # 更新結果\n",
    "            # key不存在 則默認val=0 + 1 、key在 則 val +=1\n",
    "            # ~>若再下次出現\"同餘\"時，\"同餘\"出現3次，會有兩種可能性\n",
    "            # ~>若再下次出現\"同餘\"時，\"同餘\"出現4次，會有三種可能性...\n",
    "            dic[pre_sum] = dic.get(pre_sum, 0) + 1\n",
    "\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        count = 0\n",
    "        prefix_sum = 0\n",
    "        freq = {0 : 1}\n",
    "\n",
    "        for num in nums:\n",
    "            prefix_sum = (prefix_sum + num) % k\n",
    "            if prefix_sum in freq:\n",
    "                count += freq[prefix_sum]\n",
    "            freq[prefix_sum] = freq.get(prefix_sum, 0) + 1\n",
    "        \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        record = {0:1}\n",
    "        for i in range(n):\n",
    "            count+=nums[i]\n",
    "            mod = count%k\n",
    "            same = record.get(mod,0)\n",
    "            ans += same\n",
    "            record[mod] = same+1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total, ans = 0, 0\n",
    "        for elem in nums:\n",
    "            total += elem\n",
    "            modulus = total % k\n",
    "            same = record.get(modulus, 0)\n",
    "            ans += same\n",
    "            record[modulus] = same + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        len_nums = len(nums)\n",
    "        mp = {0: 1}\n",
    "        pre_sum = 0\n",
    "        res_count = 0\n",
    "        for i in range(len_nums):\n",
    "            pre_sum = (pre_sum + nums[i]) % k\n",
    "\n",
    "            pre_sum_count = mp.get(pre_sum, 0)\n",
    "            res_count += pre_sum_count\n",
    "            mp[pre_sum] = pre_sum_count + 1\n",
    "\n",
    "        return res_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "    \n",
    "\n",
    "        pre_sum_mod=0\n",
    "        ans=0\n",
    "        #count=[0 for i in range(k)]\n",
    "\n",
    "        count={0:1}\n",
    "\n",
    "        for i in range(0,len(nums)):\n",
    "            cur=nums[i]\n",
    "            #pre_sum+=cur\n",
    "            pre_sum_mod=(pre_sum_mod+cur)%k\n",
    "\n",
    "            # if(pre_sum_mod<0):\n",
    "            #     pre_sum_mod+=k \n",
    "                \n",
    "            #if(pre_sum_mod==0 and count[0]==0):\n",
    "            #    ans+=1\n",
    "            \n",
    "            same=count.get(pre_sum_mod,0)\n",
    "            ans+=same\n",
    "            count[pre_sum_mod]=same+1\n",
    "           \n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "           \n",
    "\n",
    "\n",
    "        return sum(dp[1:])\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        ans, sumi = 0, 0\n",
    "        record = {0:1}\n",
    "        for i in nums:\n",
    "            sumi += i\n",
    "            mod = sumi % k\n",
    "            same = record.get(mod, 0)\n",
    "            ans += same\n",
    "            record[mod] = same + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0 \n",
    "        presum_dict = {0: 1}\n",
    "        presum = 0\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            presum += n \n",
    "            presum = presum % k\n",
    "            res += presum_dict.get(presum, 0)\n",
    "            presum_dict[presum] = presum_dict.get(presum, 0) + 1 \n",
    "        \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        dic = {0:1}\n",
    "        cur = 0\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            cur += num\n",
    "            ans += dic.get(cur%k,0) \n",
    "            dic[cur%k] = dic.get(cur%k,0)+1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        record = {0:1}\n",
    "        for i in range(n):\n",
    "            count+=nums[i]\n",
    "            mod = count%k\n",
    "            same = record.get(mod,0)\n",
    "            ans += same\n",
    "            record[mod] = same+1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        d = {}\n",
    "        d[0] = 1\n",
    "        res = 0\n",
    "        sum_ = 0\n",
    "        for num in nums:\n",
    "            sum_ += num\n",
    "            t = sum_ % k\n",
    "            if t in d:\n",
    "                res += d[t]\n",
    "                d[t] += 1\n",
    "            else:\n",
    "                d[t] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        l = [0]*n\n",
    "        res = 0\n",
    "        a = {0:1}\n",
    "        for i in range(n):\n",
    "            res = (res + nums[i]) % k\n",
    "            if res in a:\n",
    "                a[res] += 1\n",
    "            else:\n",
    "                a[res] = 1\n",
    "        ans = 0\n",
    "        for va in a.values():\n",
    "            ans += (va-1)*va//2\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        curr_sum = 0\n",
    "        remain_dict = {0: 1}\n",
    "        cnt = 0\n",
    "        for ele in nums:\n",
    "            curr_sum = curr_sum + ele\n",
    "            curr_remain = curr_sum % k\n",
    "            if curr_remain in remain_dict:\n",
    "                cnt = cnt + remain_dict[curr_remain]\n",
    "            if curr_remain in remain_dict:\n",
    "                remain_dict[curr_remain] += 1\n",
    "            else:\n",
    "                remain_dict[curr_remain] = 1\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0:1}\n",
    "        temp = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp += nums[i]\n",
    "            modulus = temp%k \n",
    "            same = record.get(modulus,0)\n",
    "            ans += same\n",
    "            record[modulus] = same + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        hashmap = defaultdict(int)\n",
    "        hashmap[0] = 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            r = presum[i+1] % k\n",
    "            ans += hashmap[r]\n",
    "            hashmap[r] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        hashmap = {0: 1}\n",
    "        reminder = 0\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            reminder = (reminder + x) % k\n",
    "            #get or default\n",
    "            ans += hashmap.get(reminder, 0)\n",
    "            hashmap[reminder] = hashmap.get(reminder, 0) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = defaultdict(int)\n",
    "        record[0] = 1\n",
    "        temp = 0\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            temp = (temp+nums[i])%k\n",
    "            ans += record[temp]\n",
    "            record[temp] += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        # 同余定理\n",
    "        record = {0: 1}\n",
    "        total, ans = 0, 0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "            mod = total % k\n",
    "            same = record.get(mod, 0)\n",
    "            ans += same\n",
    "            record[mod] = same + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        # dict = {0:1}\n",
    "        # res,sum,modulus = 0,0,0\n",
    "        # for num in nums:\n",
    "        #     sum += num\n",
    "        #     # modulus = sum % k \n",
    "        #     modulus = ( modulus + num % k ) % k\n",
    "        #     res += dict.get(modulus, 0)\n",
    "    \n",
    "        #     dict[modulus] =dict.get(modulus, 0) + 1\n",
    "        # return res\n",
    "\n",
    "\n",
    "        dic = {0 :1}\n",
    "        res, presum = 0,0\n",
    "        for num in nums:\n",
    "            presum += num\n",
    "            module = presum % k  \n",
    "            res += dic.get(module, 0) \n",
    "            dic[module] = dic.get(module, 0) + 1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        cursum = 0\n",
    "        curmod = 0\n",
    "        mem = [0] * k\n",
    "        mem[0] = 1\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            cursum = cursum + nums[i]\n",
    "            curmod = cursum % k\n",
    "            ans += mem[curmod]\n",
    "            mem[curmod] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        ans, sumi = 0, 0\n",
    "        record = {0:1}\n",
    "        for i in nums:\n",
    "            sumi += i\n",
    "            mod = sumi % k\n",
    "            same = record.get(mod, 0)\n",
    "            ans += same\n",
    "            record[mod] = same + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        hashmap = {0: 1}\n",
    "        reminder = 0\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            reminder = (reminder + x) % k\n",
    "            ans += hashmap.get(reminder, 0)\n",
    "            hashmap[reminder] = hashmap.get(reminder, 0) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, A: List[int], k: int) -> int:\n",
    "        if not A:\n",
    "            return 0\n",
    "\n",
    "        recorder = {0: 1}  # map_remainder_count; 初始化\n",
    "        presum = 0\n",
    "\n",
    "        res = 0\n",
    "        for num in A:\n",
    "            presum += num\n",
    "            remainder = (presum % k + k) % k\n",
    "\n",
    "            if remainder in recorder:\n",
    "                res += recorder[remainder]\n",
    "            \n",
    "            recorder[remainder] = recorder.get(remainder, 0) + 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        pre = 0\n",
    "        dic[0] = 1\n",
    "        ans = 0\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            ans += dic[pre % k]\n",
    "            dic[pre % k] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        pre_dic = collections.defaultdict(int)\n",
    "        pre_dic[0] = 1\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            ans += pre_dic[pre % k]\n",
    "            pre_dic[pre % k] += 1\n",
    "        print(pre_dic)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        dic = {0:1}\n",
    "        presum, count = 0,0\n",
    "        for num in nums:\n",
    "            presum += num\n",
    "            mod = presum%k\n",
    "            count += dic.get(mod,0)\n",
    "            dic[mod] = dic.get(mod,0)+1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0 \n",
    "        presum_dict = {0: 1}\n",
    "        presum = 0\n",
    "\n",
    "        for i, n in enumerate(nums):\n",
    "            presum += n \n",
    "            presum = presum % k\n",
    "            res += presum_dict.get(presum, 0)\n",
    "            presum_dict[presum] = presum_dict.get(presum, 0) + 1 \n",
    "        \n",
    "        return res \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        dict1 = dict(zip(list(range(k)),[1]+[0]*(k-1)))\n",
    "        cumsum = 0\n",
    "        # if len(nums) == 0:\n",
    "        #     return 0\n",
    "        for nu in nums:\n",
    "            cumsum = (cumsum + nu) % k\n",
    "            res += dict1[cumsum]\n",
    "            dict1[cumsum] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        dic= defaultdict(int)\n",
    "        dic[0]=1\n",
    "        ans = 0\n",
    "        sums =0\n",
    "        for x in nums:\n",
    "            sums += x\n",
    "            sums %= k\n",
    "            ans += dic.get(sums,0)\n",
    "            dic[sums]+=1\n",
    "\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        ans = 0\n",
    "        presum = 0\n",
    "        cnts = defaultdict(int)\n",
    "        cnts[0] = 1\n",
    "        for num in nums:\n",
    "            presum += num\n",
    "            presum %= k\n",
    "            if cnts[presum]:\n",
    "                ans += cnts[presum]\n",
    "            cnts[presum] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        dic = collections.defaultdict(int)\n",
    "        dic[0] = 1\n",
    "        ans = 0\n",
    "        pre = 0\n",
    "        for num in nums:\n",
    "            pre += num\n",
    "            ans += dic[pre % k]\n",
    "            dic[pre % k] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total = 0\n",
    "        for elem in nums:\n",
    "            total += elem\n",
    "            modulus = total % k\n",
    "            record[modulus] = record.get(modulus, 0) + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for x, cx in record.items():\n",
    "            ans += cx * (cx - 1) // 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        sum_list = [0]\n",
    "        hush_list = []\n",
    "        for i in range(k):\n",
    "            hush_list.append(0)\n",
    "        hush_list[0] = 1\n",
    "        for i in range(len(nums)):\n",
    "            sum_list.append(sum_list[i] + nums[i])\n",
    "            hush_list[sum_list[i + 1] % k] = hush_list[sum_list[i + 1] % k] + 1\n",
    "        ans = 0\n",
    "        for i in range(k):\n",
    "            ans = ans + hush_list[i] * (hush_list[i] - 1) / 2\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total = 0\n",
    "        for num in nums:\n",
    "            total += num\n",
    "            mod = total % k\n",
    "            record[mod] = record.get(mod, 0) + 1\n",
    "        \n",
    "        ans = 0\n",
    "        for x, c in record.items():\n",
    "            ans += c * (c-1) // 2       # 取两个同桶的前缀和相减\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        total, ans = 0, 0\n",
    "        for elem in nums:\n",
    "            total += elem\n",
    "            modulus = total % k\n",
    "            same = record.get(modulus, 0)\n",
    "            ans += same\n",
    "            record[modulus] = same + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        dic = {0: 1}\n",
    "        preSums = [0]\n",
    "        count = 0\n",
    "        for num in nums:\n",
    "            currentSum = num + preSums[-1]\n",
    "            preSums.append(currentSum)\n",
    "            if currentSum % k in dic:\n",
    "                count = count + dic[currentSum % k]\n",
    "            dic[currentSum % k] = dic.get(currentSum % k, 0) + 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        res = presummodk = 0\n",
    "        mp = {0: 1}\n",
    "        for num in nums:\n",
    "            presummodk = (presummodk + num) % k\n",
    "            if presummodk in mp:\n",
    "                res += mp[presummodk]\n",
    "                mp[presummodk] += 1\n",
    "            else:\n",
    "                mp[presummodk] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums, k):\n",
    "        length = len(nums)\n",
    "        start = 0\n",
    "        res = {}\n",
    "        cnt = 0\n",
    "        while start < length - 1:\n",
    "            nums[start+1] += nums[start]\n",
    "            start += 1\n",
    "\n",
    "        for num in nums:\n",
    "            if num % k == 0:\n",
    "                cnt += 1\n",
    "            if num % k in res.keys():\n",
    "                cnt += res[num % k]\n",
    "            res[num % k] = res.get(num % k, 0) + 1\n",
    "            \n",
    "        return cnt\n",
    "\n",
    "nums = [4,5,0,-2,-3,1]\n",
    "k = 5\n",
    "s = Solution()\n",
    "print(s.subarraysDivByK(nums, k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        ans, cnt, map = 0, 0, {0:1}\n",
    "        for i, num in enumerate(nums):\n",
    "            cnt += num\n",
    "            key = (cnt % k + k) % k\n",
    "            if key in map.keys():\n",
    "                ans += map[key]\n",
    "            if key in map.keys():\n",
    "                map[key]+=1\n",
    "            else:\n",
    "                map[key]=1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        preSum = collections.defaultdict(int)\n",
    "        preSum[0] = 1\n",
    "\n",
    "        count = 0\n",
    "        presum = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            presum = (presum+nums[i])%k\n",
    "            \n",
    "            count += preSum[presum]\n",
    "            preSum[presum] += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "Question: given an int array nums, return the num of subarray whose sum is dividable by k\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        record = {0: 1}\n",
    "        prefix, ans = 0, 0\n",
    "        for num in nums:\n",
    "            prefix += num\n",
    "            modulus = prefix % k\n",
    "            if modulus not in record:\n",
    "                record[modulus] = 1\n",
    "                continue\n",
    "            ans += record[modulus]\n",
    "            record[modulus] += 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        pre = Counter(a % k for a in accumulate(nums))\n",
    "        return sum(comb(v, 2) for v in pre.values()) + pre[0]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\" PrefixSum + HashTable \"\"\"\n",
    "\n",
    "        HashTable = {0:1}\n",
    "        prefixSum = 0 \n",
    "        ans = 0\n",
    "\n",
    "        for num in nums:\n",
    "            prefixSum += num\n",
    "            modd = prefixSum % k \n",
    "            freq = HashTable.get(modd, 0)\n",
    "            ans += freq\n",
    "            HashTable[modd] = freq + 1\n",
    "            \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        map = defaultdict(int)\n",
    "        map[0] = 1\n",
    "        sum = 0\n",
    "        for i in range(n):\n",
    "            sum = sum + nums[i]\n",
    "            res = sum % k\n",
    "            map[res] +=1\n",
    "        ans = 0\n",
    "        for x in map:\n",
    "            ans += int(map[x] * (map[x] - 1) / 2)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        # 用hash表记录模值出现的次数\n",
    "        records = dict({0: 1})\n",
    "        prefix_sum = 0\n",
    "        result = 0\n",
    "        for num in nums:\n",
    "            # 求出每个元素对应的的前缀和\n",
    "            prefix_sum += num\n",
    "            # 求出每个元素的前缀和对K的模\n",
    "            mod = prefix_sum % k\n",
    "            # 模值出现的次数\n",
    "            count = records.get(mod, 0)\n",
    "            # 累加次数\n",
    "            result += count\n",
    "            # 更新hash表中保存的次数\n",
    "            records[mod] = count + 1\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        preSum = collections.defaultdict(int)\n",
    "        preSum[0] = 1\n",
    "\n",
    "        count = 0\n",
    "        presum = 0\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            presum += nums[i]\n",
    "\n",
    "            mod = presum%k\n",
    "            count += preSum[mod]\n",
    "            preSum[mod] += 1\n",
    "\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "        #判断(P[j]−P[i−1]) mod k==0,根据同余定理,只要P[j] mod k==P[i−1] mod k就可以保证上面的等式成立\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        prefix = [0]*(len(nums)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        hashmap = {}\n",
    "        res = 0\n",
    "\n",
    "        for i in prefix:\n",
    "            if i%k in hashmap:\n",
    "                res += hashmap[i%k]\n",
    "            \n",
    "            if i%k in hashmap:\n",
    "                hashmap[i%k] += 1\n",
    "            else:\n",
    "                hashmap[i%k] = 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        '''\n",
    "        prefix sum O(n)\\O(n)\n",
    "        前缀和的差可以求出任意区间的和\n",
    "\n",
    "        (prefix[j] - prefix[i]) % k == 0 \n",
    "        --> prefix[j] % k == prefix[i] % k     <<--- 同余定理\n",
    "\n",
    "        '''\n",
    "        d = {0:1}\n",
    "        s = count = 0\n",
    "        for num in nums:\n",
    "            s = (s + num) % k\n",
    "            if s in d:\n",
    "                count += d[s]\n",
    "                d[s] += 1\n",
    "            else:\n",
    "                d[s] = 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] + [0] * n\n",
    "        for i, x in enumerate(nums):\n",
    "            s[i + 1] = (s[i] + x) % k\n",
    "        d = defaultdict(int)\n",
    "        d[0] = 1\n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans += d[s[i]]\n",
    "            d[s[i]] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        prefixsum = [0] * (n+1)\n",
    "        modmap = {0: 1}\n",
    "        for i in range(n):\n",
    "            prefixsum[i+1] = prefixsum[i] + nums[i]\n",
    "            mod = prefixsum[i+1] % k\n",
    "            if modmap.get(mod) != None:\n",
    "                ans += modmap[mod]\n",
    "                modmap[mod] += 1\n",
    "            else:\n",
    "                modmap[mod] = 1\n",
    "            # print(mod, modset, ans)\n",
    "        # print(prefixsum)\n",
    "        # print(modset)\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums, k: int) -> int:\n",
    "        len_num = len(nums)\n",
    "        sum_last = 0\n",
    "        sum_dict = {0: 1}\n",
    "        res = 0\n",
    "\n",
    "        for i in range(len_num):\n",
    "            \n",
    "            sum_last += nums[i]\n",
    "            target = sum_last % k\n",
    "            if target in sum_dict:\n",
    "                res += sum_dict[target]\n",
    "\n",
    "            if sum_last % k in sum_dict:\n",
    "                sum_dict[sum_last % k] += 1\n",
    "            else:\n",
    "                sum_dict[sum_last % k] = 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\r\n",
    "        presum = 0\r\n",
    "        presums = defaultdict(int)\r\n",
    "        presums[0] =1\r\n",
    "        ans = 0\r\n",
    "        for x in nums:\r\n",
    "            presum = (presum + x)%k\r\n",
    "            ans += presums[presum]\r\n",
    "            presums[presum] += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        presum = 0\n",
    "        presums = defaultdict(int)\n",
    "        presums[0] =1\n",
    "        ans = 0\n",
    "        for x in nums:\n",
    "            presum = (presum + x)%k\n",
    "            ans += presums[presum]\n",
    "            presums[presum] += 1\n",
    "        return ans\n",
    "\n",
    "# 作者：小姜可\n",
    "# 链接：https://leetcode.cn/problems/subarray-sums-divisible-by-k/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] * (n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            presum[i+1] = presum[i] + nums[i]\n",
    "        \n",
    "        res = 0\n",
    "        mapper = defaultdict(int)\n",
    "\n",
    "        for s in presum:\n",
    "            if s % k in mapper:\n",
    "                res += mapper[s % k]\n",
    "            mapper[s % k] += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        res = [nums[0]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        return res\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        presum = self.pre_sum(nums)\n",
    "        cnt_mod = defaultdict(int)\n",
    "        total = 0\n",
    "        for num in presum:\n",
    "            mod = num % k\n",
    "            if mod == 0:\n",
    "                total += 1\n",
    "            if mod < 0:\n",
    "                mod += k\n",
    "            total += cnt_mod[mod]\n",
    "            cnt_mod[mod] += 1\n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarraysDivByK(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        prefixsum = [0] * (n+1)\n",
    "        modmap = {0: 1}\n",
    "        for i in range(n):\n",
    "            prefixsum[i+1] = prefixsum[i] + nums[i]\n",
    "            mod = prefixsum[i+1] % k\n",
    "            if modmap.get(mod) != None:\n",
    "                ans += modmap[mod]\n",
    "                modmap[mod] += 1\n",
    "            else:\n",
    "                modmap[mod] = 1\n",
    "        return ans\n",
    "            \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
